package first

/*
	找出数组中重复的数字。
	在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

	示例 1：

	输入：
	[2, 3, 1, 0, 2, 5, 3]
	输出：2 或 3
	限制：

	2 <= n <= 100000

	来源：力扣（LeetCode）
	链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
	著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/
/*
	1. 给定m=nums[i],判断m和i是否相等
	1.1 如果m==nums[i],遍历下一个
	1.2 m!=nums[i] ,判断m和nums[m]是否相等
	1.2.1 相等、则说明已经重复(nums[i],nums[m]的值都是m)
	1.2.2 不相等、则交换m和nums[m]、将m放到正确的位置
	1.3 接上面的交换结果、再次令m=nums[i]、继续比较
*/
func findRepeatNumber(nums []int) int {
	for i := 0; i < len(nums); i++ {
		m := nums[i]
		for m != i {
			if m == nums[m] {
				return m
			}
			nums[m], nums[i] = nums[i], nums[m]
			m = nums[i]
		}
	}
	return -1
}
